
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1556. -- 墓地秘密 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1556: 墓地秘密</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>8&nbsp;&nbsp;<span class=green>Solved: </span>4<br>[<a href='submitpage.php?id=1556'>Submit</a>][<a href='problemstatus.php?id=1556'>Status</a>][<a href='bbs.php?id=1556'>Discuss</a>]</center><h2>Description</h2><div class=content>费尽周折，终于将众将士的残骸运送到了KD军事基地地底层的大型墓地入口。KD的伙伴和战友们都参加了这次重大的送葬仪式。右边是一扇敞开的大门，进去便是墓地了，左边是一堵凹进去的墙，没有什么特别的地方。
部队缓缓进入右边的门，一切。。。就这么结束了么。。。。。
此时， F却没有跟上队伍，在一般MM都会有的强烈的第六感之下，她来到了左边这堵墙前一探究竟。扫去了重重的灰尘之后，墙上一块凹进去的手掌印清晰可见了。F试着用自己的手对上去，竟刚好合适。稍微用力一按，顿时一声巨响，地上马上裂开一大洞，F和那厚重的墙瞬间一起落入深渊！当其他人听见了巨大的声响而赶来的时候，一切都恢复平静了。只有那堵墙后面的世界，震惊了所有生物。这到底是什么，为什么会在墓地里面？
墙的后面是一个巨大的迷宫！简单的一行字浮现在了一侧的墙上：猛烈撞击所有发亮的机关石。当大伙好奇的蜂拥进迷宫的时候，一块莫名其妙的巨石竟从入口上方落下，将入口完全堵死了！石头上清晰的写了一行字：超过规定时间不能完成任务，全部人都会困死于此。看来，只有硬着头皮去闯，才有可能离开这里，并且探索出这个迷宫的秘密了。
于是大家马上散开，很快摸清了这里的地形，剩下的任务就是轰击石头了。那么。。。论攻击力最高的，自然非功夫DP莫属，而且功夫DP可以使用前滚翻移动法，能够瞬间获得巨大的初速度，并且在直线运动的时候速度将近似光速，质量无穷大，那动能自然就。。。。。。DP每次可以选择朝一个方向滚动，并且可以自己选择在某位置停下来，或者撞击到墙和石头的时候被迫停下来。由于直线速度过快，所以要停下来拐弯自然就是很麻烦的事情。那么只有制定出一个最好的运动方法，使得DP停下来次数最少，才能争取尽量多的时间！
</div><h2>Input</h2><div class=content>第一行3个正整数N、M和T。表示这是一个N*M的迷宫，并且有T个机关石。
接下来用一个N*M的字符矩阵描述迷宫，．表示是空地，#表示是墙。
接下来T行每行2个正整数X、Y，描述一个机关石的位置，它在迷宫对应的位置是#。不会有两个机关石在同一位置。
最后一行2个正整数X0、Y0，表示DP的初始位置。
</div><h2>Output</h2><div class=content>
一个正整数ANS，表示DP至少要停下来多少次才能撞击完所有的机关石。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 6 3<br />
……<br />
….#.<br />
…..#<br />
….#.<br />
2 5<br />
3 6<br />
4 5<br />
1 5<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>5<br />
</span></div><h2>HINT</h2>
			<div class=content><p>数据规模：<br />
对于10%的数据，N、M<=10，T<=2；<br />
对于40%的数据，N、M<=50，T<=10；<br />
对于100%的数据，N、M<=100，T<=15；<br />
注意事项：<br />
迷宫的最外层是墙，即任何时候不可能滚出迷宫，墙是撞不烂的（好硬）！<br />
每次DP只能选择4个基本方向中的一个方向移动，每块机关石都必须被撞击，撞击后变成普通的墙。<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=HNOI2009集训Day8'>HNOI2009集训Day8</a></p></div><center>[<a href='submitpage.php?id=1556'>Submit</a>][<a href='problemstatus.php?id=1556'>Status</a>][<a href='bbs.php?id=1556'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
